package com.wpp.data_structure.queue;

import com.wpp.data_structure.MyNode;
import com.wpp.data_structure.stack.DefaultStack;

import java.util.Stack;

/**
 * @author wpp25
 * @date 2021/6/6 14:49
 * @description：
 */
public class BaseStackQueue<T> implements MyQueue<T>{
    /**
     * 入队（push）:
     * 新元素总是压入 s1 的栈顶，同时我们会把 s1 中压入的第一个元素赋值给作为队首元素的 front 变量
     * 出队（pop）:
     * 根据栈 LIFO 的特性，s1 中第一个压入的元素在栈底。为了弹出 s1 的栈底元素，我们得把 s1 中所有的元素全部弹出，
     * 再把它们压入到另一个栈 s2 中，这个操作会让元素的入栈顺序反转过来。通过这样的方式，s1 中栈底元素就变成了 s2 的栈顶元素，
     * 这样就可以直接从 s2 将它弹出了。一旦 s2 变空了，我们只需把 s1 中的元素再一次转移到 s2 就可以了
     *
     * 入队 - O(1)，出队 - 摊还复杂度 O(1)
     */
    DefaultStack<T> stack1;
    DefaultStack<T> stack2;

    public BaseStackQueue() {
        stack1 = new DefaultStack<>();
        stack2 = new DefaultStack<>();
    }

    @Override
    public String print() {
        DefaultStack<T> stack3 = new DefaultStack<>();

        StringBuilder sb = new StringBuilder("队列头部 <- ");
        while (!stack2.empty()) {
            stack3.push(stack2.peek());
            sb.append(stack2.pop()).append(" ");
        }
        while ((!stack1.empty())) {
            stack2.push(stack1.pop());
        }
        while (!stack2.empty()) {
            stack3.push(stack2.peek());
            sb.append(stack2.pop()).append(" ");
        }

        stack1 = stack3;
        sb.append(" <- 队列尾部 size：").append(getSize());
        return sb.toString();
    }

    @Override
    public void add(T t) {
        stack1.push(t);
    }

    @Override
    public T poll() {
        if (stack2.empty()) {
            while (!stack1.empty()){
                stack2.push(stack1.pop());
            }
        }
        if (!stack2.empty()) {
            return stack2.pop();
        }
        return null;
    }

    @Override
    public T top() {
        if (stack2.empty()) {
            while (!(stack1.empty())){
                stack2.push(stack1.pop());
            }
        }
        if (!stack2.empty()) {
            return stack2.peek();
        }
        return null;
    }

    @Override
    public T tail() {
        return stack1.peek();
    }

    @Override
    public int getSize() {
        return stack1.size() + stack2.size();
    }
}
